|
In Boolean algebra, the algebraic normal form (ANF), Zhegalkin normal form, or Reed–Muller expansion is a way of writing logical formulas in one of three subforms: * The entire formula is purely true or false: *: 1 *: 0 * One or more variables are ANDed together into a term. One or more terms are XORed together into ANF. No NOTs are permitted: *: a ⊕ b ⊕ ab ⊕ abc *or in standard propositional logic symbols: *: * The previous subform with a purely true term: *: 1 ⊕ a ⊕ b ⊕ ab ⊕ abc Formulas written in ANF are also known as Zhegalkin polynomials ((ロシア語:полиномы Жегалкина)) and Positive Polarity (or Parity) Reed–Muller expressions. == Common uses == ANF is a normal form, which means that two equivalent formulas will convert to the same ANF, easily showing whether two formulas are equivalent for automated theorem proving. Unlike other normal forms, it can be represented as a simple list of lists of variable names. Conjunctive and disjunctive normal forms also require recording whether each variable is negated or not. Negation normal form is unsuitable for that purpose, since it doesn't use equality as its equivalence relation: a ∨ ¬a isn't reduced to the same thing as 1, even though they're equal. Putting a formula into ANF also makes it easy to identify linear functions (used, for example, in linear feedback shift registers): a linear function is one that is a sum of single literals. Properties of nonlinear feedback shift registers can also be deduced from certain properties of the feedback function in ANF. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「algebraic normal form」の詳細全文を読む スポンサード リンク
|